from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def check(x, y):
            # 检查对角线
            # 左上对角线
            i, j = x - 1, y - 1
            while i >= 0 and j >= 0:
                if path[i][j] == "Q":
                    return False
                else:
                    i -= 1
                    j -= 1
            # 右上对角线
            i, j = x - 1, y + 1
            while i >= 0 and j < n:
                if path[i][j] == "Q":
                    return False
                else:
                    i -= 1
                    j += 1
            return True

        vis = [False] * n  # 用于检查当前行，列 是否使用过
        ans = []
        path = [["."] * n for _ in range(n)]

        # 当前层，填那个元素
        def dfs(dep):
            if dep == n:
                ans.append(["".join(row) for row in path])
                return
            for j in range(n):
                if not vis[j]:
                    # 当前层 填充的元素
                    path[dep][j] = "Q"
                    vis[j] = True
                    # 检查当前是否合法
                    if check(dep, j):
                        # 递归下一层
                        dfs(dep + 1)
                    # 回溯
                    path[dep][j] = "."
                    vis[j] = False

        dfs(0)
        return ans